package leetcode;

/*
538. 把二叉搜索树转换为累加树
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 原始二叉搜索树:
      5
    /   \
   2     13
输出: 转换为累加树:
     18
    /   \
  20     13
*/

public class problems_538 {
    public static void main(String[] args) {
        TreeNode A1 = new TreeNode(2);
        TreeNode A2 = new TreeNode(0);
        TreeNode A3 = new TreeNode(3);
        TreeNode A4 = new TreeNode(-4);
        TreeNode A5 = new TreeNode(1);
        A1.left = A2;
        A1.right = A3;
        A3.left = A4;
        A4.right = A5;
        new Solution().convertBST(A1);
        System.out.println();
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        private int sum = 0;

        public TreeNode convertBST(TreeNode root) {
            if (root != null) {
                convertBST(root.right);
                sum += root.val;
                root.val = sum;
                convertBST(root.left);
            }
            return root;
        }
    }

//    static class Solution {
//        public TreeNode convertBST(TreeNode root) {
//            dfs(root, null);
//            return root;
//        }
//
//        private void dfs(TreeNode node, TreeNode parent) {
//            if (null == node) return;
//            if (null != parent) node.val = node.val + parent.val;
//            if (null != node.right) node.val = node.val + node.right.val;
//            if (null != node.right) dfs(node.right, null);
//            if (null != node.left) dfs(node.left, node);
//        }
//    }
}